package solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-08-04 18:04
 */
public class Solution_1String {

    /*===========================================================================================================================
     * 滑动窗口1  76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * 实例：s = "ADOBECODEBANC", t = "ABC"  输出"BANC"    就是说要在 S(source) 中找到包含 T(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。
     * 思路是这样：
     * 1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
     * 2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
     * 3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
     * 4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
     * */
    public String minWindow1(String s, String t) {
        if(s.length()<t.length())
            return "";
        //need记录需要凑齐的字符和个数
        HashMap<Character,Integer> need=new HashMap<>();
        //window记录窗口中当前包含的字符和个数
        HashMap<Character,Integer> window=new HashMap<>();
        char[] chars = t.toCharArray();
        for (char c:chars) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        int start=-1;
        int len=Integer.MAX_VALUE;

        //valid 变量表示窗口中满足 need 条件的各个字符有多少个，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。
        int valid=0;
        //开始进行滑动：
        /*如果一个字符进入窗口，应该增加 window 计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 valid 满足 need 时应该收缩窗口；应该在收缩窗口的时候更新最终结果。*/
        while (right<s.length()){
            //c是即将进入窗口的字符
            char c=s.charAt(right);
            right++;
            //更新窗口内的数据
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            System.out.println(String.format("window: [%d, %d)\n",left,right));
            //判断左窗口是否需要收缩
            while (valid==need.size()&&left<right){
                if (right-left<len){
                    start=left;
                    len=right-left;
                }
                char d=s.charAt(left);
                //进行窗口内的数据更新
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
                // 左移窗口
                left++;
            }
        }
        return start==-1? "":s.substring(start, start+len);
    }

    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();
    public String minWindow(String s, String t) {
        int tLen = t.length();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        while (r < sLen) {
            ++r;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                }
                ++l;
            }
        }
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
    public boolean check() {
        Iterator iter = ori.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (cnt.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }

    /*===========================================================================================================================
    * 滑动窗口2  567. 字符串的排列
    * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。
     */
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length()>s2.length())
            return false;
        //need记录需要凑齐的字符和个数
        HashMap<Character,Integer> need=new HashMap<>();
        //window记录窗口中当前包含的字符和个数
        HashMap<Character,Integer> window=new HashMap<>();
        char[] chars = s1.toCharArray();
        for (char c:chars) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        //valid 变量表示窗口中满足 need 条件的各个字符有多少个，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。
        int valid=0;
        while (right<s2.length()){
            char c=s2.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while (right-left>= s1.length()){
                if (valid==need.size()){
                    //此时字串长度和符合的字符数都等于need中的，找到合法字串，返回
                    return true;
                }
                char d=s2.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return false;
    }

    /*===========================================================================================================================
     * 滑动窗口3  438. 找到字符串中所有字母异位词
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
     * 相当于，输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
     */
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length()>s.length())
            return new LinkedList<>();
        HashMap<Character,Integer> need=new HashMap<>();
        HashMap<Character,Integer> window=new HashMap<>();
        char[] chars = p.toCharArray();
        for (char c:chars) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        int vaild=0;
        List<Integer> res=new LinkedList<>();
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    vaild++;
                }
            }
            //判断做窗口是否需要收缩
            while (right-left>=p.length()){
                //当窗口内字串符合要求时，将起始下标加入结果集
                if (vaild==need.size()){
                    res.add(left);
                }
                char d=s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (window.get(d).equals(need.get(d))){
                        vaild--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return res;
    }



    /*===========================================================================================================================
     * 滑动窗口4  3. 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> window=new HashMap<>();
        int left=0,right=0;
        int res=0;
        while (right<s.length()){
            char c=s.charAt(right);
            right++;
            window.put(c,window.getOrDefault(c,0)+1);
            while (window.get(c)>1){
                char d=s.charAt(left);
                left++;
                window.put(d,window.getOrDefault(d,0)-1);
            }
            res=Math.max(res,right-left);
        }
        return res;
    }



   /*===========================================================================================================================
    *反转字符串
    * 双指针
    * */
    public void reverseString(char[] s) {
        int n=s.length;
        int l=0,r=n-1;
        while (l<r){
                char t=s[l];
                s[l++]=s[r];
                s[r--]=t;
        }
    }

    /*===========================================================================================================================
     *整数反转
     * */
    public int reverse(int x) {
        int res=0;
        while (x!=0){
            int  t=res*10+x%10;
            //判断是否溢出，如果溢出，直接返回0
            if ((t-x%10)/10!=res){
                return 0;
            }
            res=t;
            x/=10;
        }
        return res;
    }

    /*===========================================================================================================================
     *字符串中的第一个唯一字符
     * 1.使用哈希表计数
     * 2.使用Java的api：一个从前查找，一个从后查找，如果下标相等，说明只出现了一次
     * */
  /*  public int firstUniqChar(String s) {
        char[] cs=s.toCharArray();
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < cs.length; i++) {
            map.put(cs[i],map.getOrDefault(cs[i],0)+1);
        }
        for (int i = 0; i < cs.length; i++) {
            int n=map.get(cs[i]);
            if (n==1){
                return i;
            }
        }
        return -1;
    }*/
    public int firstUniqChar(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(s.charAt(i))==s.lastIndexOf(s.charAt(i))){
                return i;
            }
        }
        return -1;
    }



    /*===========================================================================================================================
     *有效的字母异位词
     * 1.计数
     * 2.排序后直接比较
     * */
    /*public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        char[] cs=s.toCharArray();
        char[] ct=t.toCharArray();
        int[] count=new int[26];
        for (int i = 0; i < cs.length; i++) {
            count[cs[i]-'a']++;
        }
        for (int i = 0; i < ct.length; i++) {
            count[ct[i]-'a']--;
        }
        for (int c:count) {
            if (c!=0)
                return false;
        }
        return true;
    }*/

    public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        char[] cs=s.toCharArray();
        char[] ct=t.toCharArray();
        Arrays.sort(cs);
        Arrays.sort(ct);
        return Arrays.equals(cs,ct);
    }


    /*===========================================================================================================================
     *验证回文串
     * 1.双指针
     * 2.正则匹配,使用正则表达式将字符串转为小写只有字母，再将其反转，与原字符串比较
     * */
    /*public boolean isPalindrome(String s) {
        char[] cs=s.toCharArray();
        int n=cs.length;
        if (n==0){
            return true;
        }
        int l=0,r=n-1;
        while (l<r){
            while (l<r&&!Character.isLetterOrDigit(cs[l]))
                l++;
            while (l<r&&!Character.isLetterOrDigit(cs[r]))
                r--;
            if (Character.toLowerCase(cs[l])==Character.toLowerCase(cs[r])){
                l++;r--;
            }else {
                return false;
            }
        }
        return true;
    }*/

    public boolean isPalindrome(String s) {
        //特殊字符过滤掉，只留下字母和数字，然后转化为小写
        String zz=s.replaceAll("[^A-Za-z0-9]","").toLowerCase();
        //System.out.println(zz);
        String rvs=new StringBuffer(zz).reverse().toString();
        return zz.equals(rvs);
    }


    /*===========================================================================================================================
     *字符串转换整数 (atoi)
     * */
   /* public int myAtoi(String s) {
        int n=s.length();
        if (n==0||s==null){
            return 0;
        }
        int i=0;
        //记录是正数还是负数
        boolean sign=true;
        //去除空格
        while (i<n&&s.charAt(i)==' ') i++;
        if (i>=n){
            return 0;
        }
        System.out.println("i="+i);
        //判断符号
        if (s.charAt(i)=='-'||s.charAt(i)=='+'){
            if (s.charAt(i)=='-') sign=false;
            i++;
        }
        System.out.println("i="+i);
        System.out.println(sign);
        int res=0;
        while (i<n){
            //获得当前字符
            int num=s.charAt(i)-'0';
            if (num>9||num<0){
                break;
            }
            //判断是否越界
            int t=res*10+num;
            if (t/10!=res){
                if (sign) return Integer.MAX_VALUE;
                else return Integer.MIN_VALUE;
            }
            res=t;
            i++;
        }
        if(sign){
            return res;
        }else {
            return -1*res;
        }
    }*/
    public int myAtoi(String str) {
        str = str.trim();//去掉前后的空格
        //如果为空，直接返回0
        if (str.length() == 0)
            return 0;
        int index = 0;//遍历字符串中字符的位置
        int res = 0;//最终结果
        int sign = 1;//符号，1是正数，-1是负数，默认为正数
        int length = str.length();
        //判断符号
        if (str.charAt(index) == '-' || str.charAt(index) == '+')
            sign = str.charAt(index++) == '+' ? 1 : -1;
        for (; index < length; ++index) {
            //取出字符串中字符，然后转化为数字
            int digit = str.charAt(index) - '0';
            //按照题中的要求，读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。
            //字符串的其余部分将被忽略。如果读取了非数字，后面的都要忽略
            if (digit < 0 || digit > 9)
                break;
            //越界处理
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10))
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            else
                res = res * 10 + digit;
        }
        return sign * res;
    }



    /*===========================================================================================================================
     *实现 strStr()
     * 1.双指针
     * 2.截取主串
     * 3.KMP
     * */
   /* public int strStr(String haystack, String needle) {
        int n1=haystack.length(),n2=needle.length();
        System.out.println(n1+"   "+n2);
        if (n2==0) return 0;
        if (n2>n1) return -1;
        for (int i = 0; i < n1-n2+1; i++) {
            int j=i,k=0;
            while (k<n2&&haystack.charAt(j)==needle.charAt(k)){
                System.out.println("j="+j+"    k="+k);
                j++;k++;
            }
            System.out.println("j="+j+"    k="+k);
            if (k==n2)
                return i;
        }
        return -1;
    }*/
    public int strStr(String haystack, String needle) {
        int n1=haystack.length(),n2=needle.length();
        System.out.println(n1+"   "+n2);
        if (n2==0) return 0;
        if (n2>n1) return -1;
        for (int i = 0; i < n1-n2+1; i++) {
            if (haystack.substring(i,i+n2).equals(needle)){
                return i;
            }
        }
        return -1;
    }


    /*===========================================================================================================================
     *外观数列
     * 递归调用
     * */
    public String countAndSay(int n) {
        if (n==1){
            //System.out.println("n="+n+"   res="+1);
            return "1";
        }
        String s=countAndSay(n-1);
        int cnt=0;
        //System.out.println("sl="+s.length());
        char nowc=s.charAt(0);
       // System.out.println("nowc="+nowc);
        StringBuffer res=new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)==nowc){
                cnt++;
            }else {
                res.append(cnt);
                res.append(nowc);
                cnt=1;
                nowc=s.charAt(i);
            }
        }
        res.append(cnt);
        res.append(nowc);
        //System.out.println("n="+n+"   res="+res.toString());
        return res.toString();
    }


    /*===========================================================================================================================
     *最长公共前缀
     * */
    public String longestCommonPrefix(String[] strs) {
        int n=strs.length;
        int n0=strs[0].length();
        for (int i = 0; i < n0; i++) {
            //以第0个字符串的第i个字符为基准进行对比
            char c=strs[0].charAt(i);
            //循环判断第j个字符串的第i和字符是否与c相同，或者第j个字符串长度是否够
            for (int j = 1; j < n; j++) {
                if (strs[j].length()<=i||strs[j].charAt(i)!=c){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }

  public static void main(String[] args) {
//      int[] nums1=new int[]{3,2,4};
//      int[] nums2=new int[]{2,2};
        //char[] s=new char[]{'h','e','l','l','o'};
        String haystack = "a", needle = "a";
        //String s2 = "ADOBECODEBANC";
        String t="ABC";
        String[] strs = {"ab", "a"};
        // String columnTitle = "AB";


      String s1="ab" ;
      String s2="eidbaooo";

//        Solution_1String object=new Solution_1String();
        //object.reverseString(s);
//      System.out.println(object.reverse(1534236469));
//      System.out.println(object.firstUniqChar(s));
//      System.out.println(object.isAnagram(s1,s2));
//      System.out.println(object.isPalindrome(s1));
//        System.out.println(object.myAtoi(s1));
//        System.out.println(object.strStr(haystack,needle));
//        System.out.println(object.countAndSay(4));
        //System.out.println(object.longestCommonPrefix(strs));
      //System.out.println(object.minWindow(s2,t));
//      System.out.println(object.checkInclusion(s1,s2));


        //System.out.println(res);
        /*for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }*/
      /*  for (char r:s) {
            System.out.println(r);
        }*/

    }
}
